package org.ala.linshen.dp;

/**
 * 给定一个整数数组 arr 和一个整数 k ，通过重复 k 次来修改数组。
 *
 * 例如，如果 arr = [1, 2] ， k = 3 ，那么修改后的数组将是 [1, 2, 1, 2, 1, 2] 。
 *
 * 返回修改后的数组中的最大的子数组之和。注意，子数组长度可以是 0，在这种情况下它的总和也是 0。
 *
 * 由于 结果可能会很大，需要返回的 109 + 7 的 模 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：arr = [1,2], k = 3
 * 输出：9
 * 示例 2：
 *
 * 输入：arr = [1,-2,1], k = 5
 * 输出：2
 * 示例 3：
 *
 * 输入：arr = [-1,-2], k = 7
 * 输出：0
 *
 *
 * 提示：
 *
 * 1 <= arr.length <= 105
 * 1 <= k <= 105
 * -104 <= arr[i] <= 104
 *
 * @author ala
 * @date 2024-09-15 18:04
 */
public class Q1191 {
    public static void main(String[] args) {
        Q1191 q = new Q1191();

//        int[] arr = {1,2};
//        int k = 3;

//        int[] arr = {1, -2, 1};
//        int k = 5;

//        int[] arr = {-1, -2};
//        int k = 7;

//        int[] arr = {-7, -1, 5, 2, 3, -7, -6, 1};
//        int k = 6;

//        int[] arr = {-5,-2,0,0,3,9,-2,-5,4};
//        int k = 5;

        int[] arr = {1, -1};
        int k = 1;

        System.out.println(q.kConcatenationMaxSum(arr, k));
    }
    public int kConcatenationMaxSum(int[] arr, int k) {
        return V1(arr, k);
    }
    static int MOD = (int)1e9 + 7;

    /**
     * 1）如果 k == 1，直接对arr最大子和
     * 2）如果 k >= 2，对2arr最大子和
     *      如果 sum <= 0，则最大子和就是arr
     *      如果 sum > 0，则最大子和 = 2arr的最大子和 + (k - 2) * sum
     *          因为2arr的最大子和被截成两段，前一段 + 中间(k - 2)个arr + 后一段
     */
    protected int V1(int[] arr, int k) {
        if (k == 1) {
            return (int)(maxSubSum(arr) % MOD);
        }

        int N = arr.length;
        long sum = 0;
        int[] arr2 = new int[N << 1];
        for (int i = 0 ; i < N ; i++) {
            arr2[i] = arr2[i + N] = arr[i];
            sum += arr[i];
        }
        long a = maxSubSum(arr2);

        return sum <= 0 ? (int)(a % MOD) : (int)(a % MOD + (k - 2) * sum % MOD) % MOD;
    }
    protected long maxSubSum(int[] arr) {
        int N = arr.length;
        //  对arr2求最大子和
        long p = Math.max(arr[0], 0), mx = p;
        for (int i = 1 ; i < N ; i++) {
            long v = Math.max(p + arr[i], arr[i]);
            v = Math.max(v, 0);
            mx = Math.max(mx, v);
            p = v;
        }
        return mx;
    }
}
